`
https://leetcode.cn/problems/maximum-path-score-in-a-grid/
`

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number}
 */
var maxPathScore = function (grid, k) {
  const m = grid.length, n = grid[0].length
  const memo = Array.from({ length: m }, () => Array.from({ length: n }, () => new Array(k + 1).fill(-1)))
  const dfs = (i, j, k) => {
    if (i < 0 || j < 0 || k < 0) return -Infinity
    if (i === 0 && j === 0) return 0 // 题目保证 grid[0][0] === 0
    if (memo[i][j][k] !== -1) return memo[i][j][k]
    const x = grid[i][j]
    const newK = x > 0 ? k - 1 : k;
    return memo[i][j][k] = Math.max(dfs(i - 1, j, newK), dfs(i, j - 1, newK)) + x
  }
  const res = dfs(m - 1, n - 1, k)
  return res < 0 ? -1 : res
};